/**
 * @file 647.PalindromeSubstr.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-19
 * 
 * @copyright Copyright (c) 2021
 * 
 * 回文子串
 * 647.回文子串
 * 5.最长回文子串
 * 516.最长回文子序列
 * 
 * 132.分割回文串II
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 647. 回文子串的数目 不去重
    int countSubstrings(string s)
    {
        // dp[i][j] [i,j]区间内的子串是否回文 左闭右闭
        // if s[i]==s[j]:
        // if 区间长度为1或2，自然回文
        // if 区间长度>=3 取决于两区间往中间走即dp[i+1,j-1]
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
            ++cnt;
        }
        for (int i = n - 1; i >= 0; --i) { // 后->前
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i + 1 == j) {
                        ++cnt;
                        dp[i][j] = true;
                        // cout << s.substr(i, j - i + 1) << endl;
                    } else if (dp[i + 1][j - 1]) {
                        ++cnt;
                        dp[i][j] = true;
                        // cout << s.substr(i, j - i + 1) << endl;
                    }
                }
            }
        }
        return cnt;
    }
    // 5.最长回文子串
    string longestPalindrome(string s)
    {
        // 布尔数组 dp[i][j] [i,j]区间内子串是否回文
        // s[i]==s[j]
        // 若区间长度1或2，自然回文
        // >=3取决于dp[i+1][j-1]
        int n = s.length();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        int distance = 0;
        int left = 0;
        // 边界可以留在循环里
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                        if (distance < j - i + 1) {
                            distance = j - i + 1;
                            left = i;
                        }
                    } else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (distance < j - i + 1) {
                            distance = j - i + 1;
                            left = i;
                        }
                    }
                }
            }
        }
        return s.substr(left, distance);
    }
    // 516.最长回文子序列
    int longestPalindromeSubseq(string s)
    {
        // dp[i][j] [i,j]区间内最长回文子序列长度
        // if s[i]==s[j] dp[i][j]=dp[i+1][j-1]+2
        // 如果s[i]!=s[j]就说明s[i]和s[j]同时加入序列对回文子序列长度没有贡献
        // 那么分别加入取最大
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // // 边界
        // for (int i = 0; i < n; ++i) {
        //     dp[i][i] = 1;
        // }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i == j) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
    // 132.
    int minCut(string s)
    {
        // dp[i] 表示前缀s[0:i]的最少分割次数
        // dp[i]=枚举0到i min(dp[j])+1 其中s[j+1:i]是个回文串<-加1就加在这
        // 当然如果s[0:i]本身就是一个回文串，dp[i]=0
        // 具体判断一个区间内的串是否回文比较费时，可以先打表
        // 先打表g[i][j] 表示[i,j]闭区间内的串是否回文
        int n = s.length();
        vector<vector<bool>> g(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    if (i == j || i + 1 == j) {
                        g[i][j] = true;
                    } else if (g[i + 1][j - 1]) {
                        g[i][j] = true;
                    }
                }
            }
        }

        vector<int> dp(n, 2000); // s 最长2000
        for (int i = 0; i < n; ++i) {
            if (g[0][i]) { // s[0:i]回文，直接等于0
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; ++j) {
                if (g[j + 1][i]) { // s[j+1:i]是回文，这里才能加1
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
};

void test647()
{
    // std::cout << Solution().countSubstrings("abc") << std::endl; // 3
    std::cout << Solution().countSubstrings("aba") << std::endl; // 3
    // std::cout << Solution().countSubstrings("aaa") << std::endl; // 6
}
void test5()
{
    std::cout << Solution().longestPalindrome("babab") << std::endl;
    std::cout << Solution().longestPalindrome("cbbd") << std::endl;
}
void test516()
{
    std::cout << Solution().longestPalindromeSubseq("bbbab") << std::endl;
    std::cout << Solution().longestPalindromeSubseq("cbbd") << std::endl;
}

int main()
{
    // test647();
    test5();
    // test516();
    return 0;
}